package LinkTest;
import java.util.ArrayList;
import  java.util.Stack;
//将一个无序链表变为有序链表
public class Sort {
    static class ListNode {
   int val;
    ListNode next = null;
    public ListNode(int val) {
      this.val = val;
    }
  }
    public ListNode sortInList (ListNode head) {
        // write code here
        if(head==null||head.next==null){
            return head;
        }
        ArrayList<Integer> list=new ArrayList<>();//动态数组
        ListNode cur=head;
        while(cur!=null){
            list.add(cur.val);
            cur=cur.next;
        }
        list.sort((a,b)->{return (a-b);});//Lambda表达式
        ListNode p=head;
        int i=0;
        while(p!=null){
            p.val=list.get(i++);
            p=p.next;
        }
        return head;
    }
    //判断是否为回文串
    public static boolean isPail (ListNode head) {
        // write code here
        if(head==null||head.next==null){
            return true;
        }
        Stack<ListNode> s=new Stack<>();
        ListNode cur=head;
        while(cur!=null){
            s.push(cur);
            cur=cur.next;
        }
        cur=head;
        while(!s.isEmpty()){
            if(s.pop().val!=cur.val){
                return false;
            }
            cur=cur.next;
        }
        return true;
    }
}
